package com.explorati.LeetCode343.integerBreak;

import java.util.Arrays;

/**
 * @ Author : Weijian_Wang
 * @ Date : Created in 21:43 2020/10/20 0020
 * @ Description ：记忆化搜索解法
 */
public class Solution1 {

    private int[] memo;

    //将n进行分割(至少分割两部分)，可以获得的最大乘积
    private int breakInteger(int n) {

        if(n == 1) {
            return 1;
        }

        if(memo[n] != -1) {
            return memo[n];
        }

        int res = 1;
        //n能分割为i + (n - i)
        for(int i = 1; i < n; i ++) {
            // i * (n - i)
            res = max(res, i * (n-i), i * breakInteger(n - i));
        }
        memo[n] = res;
        return res;
    }

    private int max(int a, int b, int c) {
        return Math.max(a, Math.max(b, c));
    }

    public int integerBreak(int n) {
        assert(n >= 2);
        memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return breakInteger(n);
    }
}
